package FourthWeek;

import java.util.*;

public class Saturday {
    //350、两个数组的交集II
    public int[] intersect(int[] nums1, int[] nums2) {
        if (nums1.length > nums2.length) {
            //找长度最小的数组，我们返回的数组一定比这个数组长度小于等于
            return intersect(nums2,nums1);
        }
        HashMap<Integer,Integer> hash1 = new HashMap<>();
        //把长度小的数组都放到哈希表中
        for (int x : nums1) {
            hash1.put(x,hash1.getOrDefault(x,0) + 1);
        }

        int[] ret = new int[nums1.length];
        int index = 0;

        for (int n2 : nums2) {
            int count = hash1.getOrDefault(n2,0);
            if (count > 0) {
                ret[index++] = n2;
                count--;
                if (count > 0) {
                    //说明还有没有减掉的数值，更新value
                    hash1.put(n2,count);
                }else {
                    //说明这个n2在hash1中已经没有了，直接删除
                    hash1.remove(n2);
                }
            }
        }
        //返回的这个数组可能最后的长度是没有创建的时大的，所以我们要截取有效长度
        return Arrays.copyOfRange(ret,0,index);
    }

    //349、两个数组的交集I
    public int[] intersection(int[] nums1, int[] nums2) {
        HashSet<Integer> hash1 = new HashSet<>();
        HashSet<Integer> hash2 = new HashSet<>();
        for (int n1 : nums1) {
            hash1.add(n1);
        }
        for (int n2 : nums2) {
            if (hash1.contains(n2)) {
                hash2.add(n2);
            }
        }
        int[] ret = new int[hash2.size()];
        int index = 0;
        for (int x : hash2) {
            ret[index++] = x;
        }
        return ret;
    }

    //2089、找出数组排序后的目标下标
    public List<Integer> targetIndices(int[] nums, int target) {
        List<Integer> ret = new LinkedList<>();
        //我们记录下来小于 target 的数字的个数，和 等于 target的个数，
        //当这个数组是有序的时候呢，target这个数前面都是小于target的数，再加上我们记录的target的个数，它们相加就是小于等于target的长度
        int count0 = 0,count1 = 0;
        for (int i = 0;i < nums.length;i++) {
            if (nums[i] < target) {
                count0++;
            }
            if (nums[i] == target) {
                count1++;
            }
        }
        for (int i = count0;i < count0 + count1;i++) {
            ret.add(i);
        }
        return ret;
    }
    public List<Integer> targetIndices1(int[] nums, int target) {
        List<Integer> ret = new LinkedList<>();
        //先排序，在进行对其查询
        Arrays.sort(nums);
        for (int i = 0;i < nums.length;i++) {
            if (nums[i] == target) {
                ret.add(i);
            }
        }
        return ret;
    }
}
